package com.xiyou.week04.bfs;

import java.util.*;

/**
 * 433. 最小基因变化
 *
 * @ClassName：MinMutation
 * @Author：西柚
 * @Date：2022/1/21 12:09 上午
 * @Versiion：1.0
 */
public class MinMutation {

    Map<String, Integer> depth = new HashMap<String, Integer>();
    HashSet<String> hashBank = new HashSet<String>();
    Queue<String> q = new LinkedList<String>();

    /**
     * start: "AACCGGTT"
     * end:   "AACCGGTA"
     * bank: ["AACCGGTA"]
     * <p>
     * 返回值: 1
     *
     * @param start
     * @param end
     * @param bank
     * @return
     */
    public int minMutation(String start, String end, String[] bank) {
        depth.put(start, 0);

        for (String seq : bank) {
            hashBank.add(seq);
        }

        if (!hashBank.contains(end)) {
            return -1;
        }
        q.add(start);
        char[] gene = {'A', 'C', 'G', 'T'};
        while (!q.isEmpty()) {
            String s = q.peek();
            for (int i = 0; i < 8; i++) {
                for (int j = 0; j < 4; j++) {
                    if (s.toCharArray()[i] != gene[j]) {
                        String ns = s;
                        ns.toCharArray()[i] = gene[j];
                        if (!hashBank.contains(ns)) {
                            continue;
                        }
                        if (!depth.containsKey(ns)) {
                            continue;
                        }
                        depth.put(ns, depth.get(s) + 1);
                        q.add(ns);
                        if (ns.equals(end)) {
                            return depth.get(ns);
                        }
                    }
                }
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        MinMutation minMutation = new MinMutation();
        System.out.println(minMutation.minMutation("AACCGGTT", "AACCGGTA", new String[]{"AACCGGTA"}));
    }

}
